820 - Internet bandwidth/820.3.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  23 #define D(x) cout << #x " is " << x << endl
  24
  25 const int MAXE = 1000; //Max number of edges
  26 const int oo = INT_MAX / 2 - 1;
  27 int cap[MAXE];
  28 int first[MAXE];
  29 int next[MAXE];
  30 int adj[MAXE];
  31 int current_edge;
  32
  33 /*
  34   Builds a directed edge (u, v) with capacity c.
  35   Note that actually two edges are added, the edge
  36   and its complementary edge for the backflow.
  37  */
  38 int add_edge(int u, int v, int c){
  39   adj[current_edge] = v;
  40   cap[current_edge] = c;
  41   next[current_edge] = first[u];
  42   first[u] = current_edge++;
  43
  44   adj[current_edge] = u;
  45   cap[current_edge] = 0;
  46   next[current_edge] = first[v];
  47   first[v] = current_edge++;
  48 }
  49
  50 void initialize_max_flow(){
  51   current_edge = 0;
  52   memset(next, -1, sizeof next);
  53   memset(first, -1, sizeof first);
  54 }
  55
  56 int q[MAXE];
  57 int incr[MAXE];
  58 int arrived_by[MAXE]; //arrived_by[i] = The last edge used to reach node i
  59 int find_augmenting_path(int src, int snk){
  60   /*
  61     Make a BFS to find an augmenting path from the source to the sink.
  62     Then pump flow through this path, and return the amount that was pumped.
  63   */
  64   memset(arrived_by, -1, sizeof arrived_by);
  65   int h = 0, t = 0;
  66   q[t++] = src;
  67   arrived_by[src] = -2;
  68   incr[src] = oo;
  69   while (h < t && arrived_by[snk] == -1){ //BFS
  70     int u = q[h++];
  71     for (int e = first[u]; e != -1; e = next[e]){
  72       int v = adj[e];
  73       if (arrived_by[v] == -1 && cap[e] > 0){
  74         arrived_by[v] = e;
  75         incr[v] = min(incr[u], cap[e]);
  76         q[t++] = v;
  77       }
  78     }
  79   }
  80
  81   if (arrived_by[snk] == -1) return 0;
  82
  83   int cur = snk;
  84   int neck = incr[snk];
  85   while (cur != src){
  86     //Remove capacity from the edge used to reach node "cur"
  87     //Add capacity to the backedge
  88     cap[arrived_by[cur]] -= neck;
  89     cap[arrived_by[cur] ^ 1] += neck;
  90     cur = adj[arrived_by[cur] ^ 1]; //move backwards in the path
  91   }
  92   return neck;
  93 }
  94
  95 int max_flow(int src, int snk){
  96   int ans = 0, neck;
  97   while ((neck = find_augmenting_path(src, snk)) != 0){
  98     ans += neck;
  99   }
 100   return ans;
 101 }
 102
 103
 104 int main(){
 105   int n, Case = 1;
 106   while (scanf("%d", &n)==1 && n){
 107     initialize_max_flow();
 108     int src, snk, e;
 109     scanf("%d %d %d", &src, &snk, &e);
 110     while (e--){
 111       int u, v, c;
 112       scanf("%d %d %d", &u, &v, &c);
 113       add_edge(u, v, c);
 114       add_edge(v, u, c);
 115     }
 116     printf("Network %d\n", Case++);
 117     printf("The bandwidth is %d.\n\n", max_flow(src, snk));
 118   }
 119   return 0;
 120 }